SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Simplex graph</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Simplex graph</span></span>

</h1>

</header>

<p>In <a href="Graph_theory" title="Graph theory">graph theory</a>, a branch of <a href="Mathematics" title="Mathematics">mathematics</a>, the <b>simplex graph</b> <span class="texhtml">κ(<i>G</i>)</span> of an <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a> <span class="texhtml mvar" style="font-style:italic;">G</span> is itself a graph, with one <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">node</a> for each <a href="Clique_(graph_theory)" title="Clique (graph theory)">clique</a> (a set of mutually adjacent vertices) in <span class="texhtml mvar" style="font-style:italic;">G</span>. Two nodes of <span class="texhtml">κ(<i>G</i>)</span> are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex.

</p><p>The empty set is included as one of the cliques of <span class="texhtml mvar" style="font-style:italic;">G</span> that are used to form the clique graph, as is every set of one vertex and every set of two adjacent vertices. Therefore, the simplex graph contains within it a <a href="Subdivision_(graph_theory)" class="mw-redirect" title="Subdivision (graph theory)">subdivision</a> of <span class="texhtml mvar" style="font-style:italic;">G</span> itself. The simplex graph of a <a href="Complete_graph" title="Complete graph">complete graph</a> is a <a href="Hypercube_graph" title="Hypercube graph">hypercube graph</a>, and the simplex graph of a <a href="Cycle_graph" title="Cycle graph">cycle graph</a> of length four or more is a <a href="Gear_graph" class="mw-redirect" title="Gear graph">gear graph</a>. The simplex graph of the <a href="Complement_graph" title="Complement graph">complement graph</a> of a <a href="Path_graph" title="Path graph">path graph</a> is a <a href="Fibonacci_cube" title="Fibonacci cube">Fibonacci cube</a>.

</p><p>The complete subgraphs of <span class="texhtml mvar" style="font-style:italic;">G</span> can be given the structure of a <a href="Median_algebra" title="Median algebra">median algebra</a>: the median of three cliques <span class="texhtml mvar" style="font-style:italic;">A</span>, <span class="texhtml mvar" style="font-style:italic;">B</span>, and <span class="texhtml mvar" style="font-style:italic;">C</span> is formed by the vertices that belong to a <a href="Majority_function" title="Majority function">majority</a> of the three cliques.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Any two vertices belonging to this median set must both belong to at least one of <span class="texhtml mvar" style="font-style:italic;">A</span>, <span class="texhtml mvar" style="font-style:italic;">B</span>, or <span class="texhtml mvar" style="font-style:italic;">C</span>, and therefore must be linked by an edge, so the median of three cliques is itself a clique. The simplex graph is the <a href="Median_graph" title="Median graph">median graph</a> corresponding to this median algebra structure. When <span class="texhtml mvar" style="font-style:italic;">G</span> is the <a href="Complement_graph" title="Complement graph">complement graph</a> of a <a href="Bipartite_graph" title="Bipartite graph">bipartite graph</a>, the cliques of <span class="texhtml mvar" style="font-style:italic;">G</span> can be given a stronger structure as a <a href="Distributive_lattice" title="Distributive lattice">distributive lattice</a>,<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> and in this case the simplex graph is the graph of the lattice. As is true for median graphs more generally, every simplex graph is itself <a href="Bipartite_graph" title="Bipartite graph">bipartite</a>.

</p><p>The simplex graph has one vertex for every simplex in the <a href="Clique_complex" title="Clique complex">clique complex</a> <span class="texhtml"><i>X</i>(<i>G</i>)</span> of <span class="texhtml mvar" style="font-style:italic;">G</span>, and two vertices are linked by an edge when one of the two corresponding simplexes is a facet of the other. Thus, the objects (vertices in the simplex graph, simplexes in <span class="texhtml"><i>X</i>(<i>G</i>)</span>) and relations between objects (edges in the simplex graph, inclusion relations between simplexes in <span class="texhtml"><i>X</i>(<i>G</i>)</span>) are in one-to-one correspondence between <span class="texhtml"><i>X</i>(<i>G</i>)</span> and <span class="texhtml">κ(<i>G</i>)</span>.

</p><p>Simplex graphs were introduced by <a href="#CITEREFBandeltvan_de_Vel1989">Bandelt & van de Vel (1989)</a>,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> who observed that a simplex graph has no cubes if and only if the underlying graph is <a href="Triangle-free_graph" title="Triangle-free graph">triangle-free</a>, and showed that the <a href="Chromatic_number" class="mw-redirect" title="Chromatic number">chromatic number</a> of the underlying graph equals the minimum number <span class="texhtml mvar" style="font-style:italic;">n</span> such that the simplex graph can be isometrically embedded into a <a href="Cartesian_product_of_graphs" title="Cartesian product of graphs">Cartesian product</a> of <span class="texhtml mvar" style="font-style:italic;">n</span> trees. As a consequence of the existence of <a href="Mycielskian" title="Mycielskian">triangle-free graphs with high chromatic number</a>, they showed that there exist two-dimensional topological <a href="Median_algebra" title="Median algebra">median algebras</a> that cannot be embedded into products of finitely many <a href="Real_tree" title="Real tree">real trees</a>. <a href="#CITEREFImrichKlavžarMulder1999">Imrich, Klavžar & Mulder (1999)</a> also use simplex graphs as part of their proof that testing whether a graph is triangle-free or whether it is a median graph may be performed equally quickly.

</p>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a href="#CITEREFBarthélemyLeclercMonjardet1986">Barthélemy, Leclerc & Monjardet (1986)</a>, page 200.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><a href="#CITEREFPropp1997">Propp (1997)</a>.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><a href="#CITEREFImrichKlavžarMulder1999">Imrich, Klavžar & Mulder (1999)</a> credit the introduction of simplex graphs to a later paper, also by Bandelt and van de Vel, but this appears to be a mistake.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBandeltChepoi2008" class="citation cs2">Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in <a href="Jacob_E._Goodman" title="Jacob E. Goodman">Goodman, J.E.</a>; Pach, J.; Pollack, R. (eds.), <i>Surveys on Discrete and Computational Geometry: Twenty Years Later</i>, Contemp. Math., vol. 453, Providence, RI: AMS, pp. <span class="nowrap">49–</span>86</cite>.</li>

<li><cite id="CITEREFBandeltvan_de_Vel1989" class="citation cs2 cs1-prop-long-vol">Bandelt, H.-J.; van de Vel, M. (1989), <a rel="nofollow" class="external text" href="https://archive.today/20130415141421/http://plms.oxfordjournals.org/cgi/content/abstract/s3-58/3/439">"Embedding topological median algebras in products of dendrons"</a>, <i>Proceedings of the London Mathematical Society</i>, s3-58 (3): <span class="nowrap">439–</span>453, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fplms%2Fs3-58.3.439">10.1112/plms/s3-58.3.439</a>, archived from <a rel="nofollow" class="external text" href="http://plms.oxfordjournals.org/cgi/content/abstract/s3-58/3/439">the original</a> on 2013-04-15</cite>.</li>

<li><cite id="CITEREFBarthélemyLeclercMonjardet1986" class="citation cs2">Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", <i>Journal of Classification</i>, <b>3</b> (2): <span class="nowrap">187–</span>224, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01894188">10.1007/BF01894188</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6092438">6092438</a></cite>.</li>

<li><cite id="CITEREFImrichKlavžarMulder1999" class="citation cs2">Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Median graphs and triangle-free graphs", <i><a href="SIAM_Journal_on_Discrete_Mathematics" title="SIAM Journal on Discrete Mathematics">SIAM Journal on Discrete Mathematics</a></i>, <b>12</b> (1): <span class="nowrap">111–</span>118, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.5906">10.1.1.28.5906</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0895480197323494">10.1137/S0895480197323494</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1666073">1666073</a></cite>.</li>

<li><cite id="CITEREFPropp1997" class="citation cs2">Propp, James (1997), "Generating random elements of finite distributive lattices", <i>Electronic Journal of Combinatorics</i>, <b>4</b> (2): R15, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math.CO/9801066">math.CO/9801066</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.37236%2F1330">10.37236/1330</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13313188">13313188</a></cite>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-06-20" href="https://en.wikipedia.org/wiki/?title=Simplex_graph&oldid=1161110585">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>